| Academic Open Internet Journal ISSN 1311-4360 |
Volume 18, 2006 |
An approach to reduce complexity in non-linear multiuser detection for DS-CDMA systems
Rekha Agarwal1, Prof.B.V.R.Reddy2* and Prof. K.K.Aggarwal3
1Rekha Agarwal is with Amity School of Engg. and Tech. . Currently she is also a research student at School of IT, Guru Gobind Singh Indra Prastha (GGSIP) University, New Delhi
2 Corresponding author: B.V.R. Reddy is working as Professor in School of IT at Guru Gobind Singh Indra Prastha University, New Delhi. (telephone: 90-011-9810909414, email: rarun96@rediffmail.com , rarun96@yahoo.com.
Postal Address: Prof. B.V.R. Reddy
School of IT,
GGSIP University, Kashmere Gate
New Delhi
Ph. No. 9810909414, 23867303, 9868230111
3 K.K. Aggarwal is currently Vice Chancellor of the Guru Gobind Singh Indra Prastha University, Kashmere Gate, New Delhi
Abstract:
We present a method to reduced complexity using switching with existing Parallel Interference Cancellation (PIC) detector based on channel characteristics. The main criterion of taking PIC detector is that it has less Bit Error Rate (BER) and less processing delay than other nonlinear multiuser detectors. This proposed detector reduces overall complexity while maintaining the same performance as PIC detector. The switching mechanism is exploited by performance complexity tradeoff between matched filter detector and PIC detector.
Key words: Multiple Access Interference, Direct Sequence Code Division Multiple Access, Signal to Noise Ratio, Signal Interference Ratio, Parallel Interference Cancellation.
I. Introduction :
In a Code Division Multiple Access (CDMA) system, several users transmit their signals simultaneously over a common channel. The receiver has knowledge of the codes of all the users. It is then required to demodulate the information symbol sequences of these users, upon reception of the sum of transmitted signals of all the users in the presence of additive noise This situation arises in a variety of communication systems such as wireless communication and other multipoint to multipoint multiple access networks. However, since multiple users share the same bandwidth to transmit data in a typical CDMA system, users signal may interfere with each other if orthogonality is not maintained and causes Multiple Access Interference (MAI). MAI degrades the performance of the system. Conventional CDMA detectors such as matched filter [1] and RAKE combiner [2] are optimized for detecting the signal of a single desired user. These conventional detectors are inefficient, because the interference is treated as noise and there is no utilization of the available knowledge of spreading sequences of the interferers. The efficiency of these detectors is dependent on the cross correlation between the spreading codes of all users.
The optimal multiuser detector, discovered by Verdu in early 1980s [3] showed that a maximum likelihood receiver could be used to optimally decode multiple users in parallel, with dramatic gains. This receiver is unfortunately, extremely complex, with the computational needs increasing as O(|AK|), where |A| is the alphabet size (2 for binary) and K is the number of users. While in many practical applications such performance complexity prohibits implementation of the Verdu algorithm, its performance is still of very much of interest since it serves as a benchmark against which to compare other schemes with less implementation complexity such as those that employ interference cancellation to be discussed shortly.
One approach is to employ a suitable linear transformation on the matched filter outputs. Belonging to this family are the decorrelating receiver and Minimum Mean Square Error (MMSE) detector [4-6]. In these methods, the different users are made uncorrelated by a linear transformation. This linear transformation is computed by measuring all cross correlations between pairs of user codes and then inverting the resulting huge matrix of cross-correlations. Since in practical systems each user is assigned a very long pseudonoise (PN) code, each bit has essentially a random code assigned to it. Thus, in this case, the above procedure would have to be repeated for each bit in succession.
Interference Cancellation (IC) schemes contribute another variant of multiuser detection and they can be broadly divided into two categories : successive cancellation and parallel cancellation. Interference cancellation should be interpreted to mean the class of techniques that demodulate and/or decode desired information, and then use this information along with channel estimates to cancel received interference from the received signal. Lower computation and hardware related structures are the main advantages of these methods beside the main advantage of lower BER or better capacity than linear multiuser detectors[2,7]. With regard to former Patel and Holtzman [8] suggested coordinated processing of the received signal with a successive cancellation scheme in which the interference caused by remaining users is removed from each user in succession.The approach successively cancels strongest users by re-encoding the decoded bits and after making an estimate of the channel, the interfering signal is recreated at the receiver and subtracted from the received waveform. In this manner successive user does not have to encounter MAI caused by initial users. One disadvantage of this scheme is the fact that a specific geometric power distribution must be assigned to the users in order that each see the same signal power to the background plus interference noise ratio. Another disadvantage of this scheme has to do with the required delay necessary to fully accomplish the IC for all the users in the system. Since the IC proceeds serially, a delay on the order of M computation stages is required to complete the job. This delay becomes intolerable for large number of users and SIC method looses its advantage.
Parallel processing of multiuser interference simultaneously removes from each user the interference produced by the remaining users accessing the channel. In this way, each user in the system receives equal treatment insofar as the attempt is made to cancel multiple user interference. As compared with the serial processing scheme, since the IC is performed in parallel for all the users, the delay required to complete the operation is at most a few bit times. Varanasi and Aazhang [9] proposed a multistage detector for an asynchronous system, where the outputs from a matched filter bank were fed into a detector that performed MAI cancellation using a multistage algorithm. At each stage in the detector, the estimates of all other users from the previous stage were used for reconstructing an estimate of the MAI and this estimate was then subtracted from the interfered signal representing the wanted bit. The computational complexity of this detector was linear with respect to number of users and delay introduced was much less than serial method [11].
A dual-mode detector that dynamically switches between matched filter and decorrelator had been studied [10]. With the above discussion in mind, this paper presents a switching mechanism that significantly reduces the computational complexity in multiuser detection. Our proposed detector switches between matched filter detector and PIC detector . In realistic situations, where the channel conditions are randomly changing, using one detector alone all the time will not be advantageous. However, if an arrangement can be made to use another detector as channel conditions change, will be definitely a better solution. The proposed detector uses conventional detector for less number of users (i.e. less MAI) as the performance of conventional detector and PIC detector is same and complexity of conventional method is much lower than PIC method. For large number of users (where BER of matched filter is much more than PIC detector) it switches to PIC detector because multiuser detection is required to reduce BER or to increase the capacity. Therefore in practical situations, when only few users are present on the channel, computational complexity can be saved by not using PIC method. This detector does not degrade the performance as the switching criterion is based on bit error rate (BER) i.e. it dyanamically switches to the detector giving less BER. The efficiency of this detector will be definitely better than if any of the two detectors is alone used all the time. Hence by exploiting the performance-complexity tradeoff between matched filter and PIC, better capacity and less BER can be achieved.
This paper is organized as follows. In section II, we present the basic model for matched filter detector and for SIC detector. In section III, we propose our switched mode detector. The results are discussed in section IV and conclusion is made in section V.
II.Basic Model: Consider a synchronous direct sequence (DS-CDMA) system with K active users. The practical DS-CDMA application is generally asynchronous (i.e. signals are randomly delayed from one another). We make the assumption that there is no multipath and all carrier phases are equal to zero. We also assume that data modulation is binary phase shift keying [2]. Assuming there are K direct users in a synchronous signal path BPSK real channel, the base band signal can be expressed as:
Where Ak(t), gk(t) and dk(t) are amplitude, signature code waveform and modulation of kth user respectively [2] and n(t) is additive while gaussian noise (AWGN), with a two sided power spectral density of No W/Hz. The power of the kth signal is square of its amplitude, which is assumed to be constant over a bit interval. The modulation consists of rectangular pulses of duration Tb (bit interval) which take on dk = ±1 values corresponding to transmitted data. We assume a total of N transmitted bits. The code waveform consists of rectangular pulses of duration Tc (“chip interval”), which pseudo randomly take on ±1 values, corresponding to same binary “pseudo-noise” (PN) code sequence [1]. The rate of code waveform, fc=1/Tc (chip rate), is much greater than the bit rate, fb=1/Tb [1]. Thus multiplying the BPSK signal at the transmitter by g(t) has the effect of spreading it out in frequency by a factor of fc / fb (hence these codes are sometimes referred to as spreading codes) [2]. For simplicity we assume that binary antipodal signals are used to transmit the information from each user. Hence, let the information sequence of the kth user be denoted by {dk(m)}, where the value of each information bit may be be ±1. The data block of kth user will be d=[dk(1)….. dk(N)]
In the conventional detection, each code waveform is regenerated and correlated with the received signal. Conventional detector also referred as matched filter detectors. The output of this is sampled at bit times, which fields “soft” estimates of the transmitted data. The final ±1 “hard” data decisions are made according to signs of soft estimates. Let us consider synchronous transmission. Then the output of correlator for the kth user for the signal in internal Tb is
where Tb is the data symbol interval, nk(t) is the correlation of noise with gk(t) .The correlation with the kth user itself give rise to the recovered data term, correlation with all other users gives rise to multiple access interference (MAI). Clearly if code sequences are orthogonal the interference from other users given by middle term vanishes and conventional single user detector is optimum [2]. The presence of MAI has a significant impact on the capacity and performance of conventional direct sequence system. As the number of interfering users increases, the amount of MAI increases. MAI also limits the error performance because of near-far effect. [2,9]. In the matrix vector notation form the output can be expressed as
y=RAD+n (4)
where R is the cross correlation matrix among all users.
III Proposed Detector: Even though the PIC detectors gives better performance than matched filter in terms of less BER or more capacity, its computational requirement is much more. Therefore, in situations when both detectors perform almost same, the computational requirement and therefore power requirement can be saved by using matched filter instead of PIC detector. As the computational complexity of the detection scheme used in a system is vital for both implementation and simulation, high complexity receiver structure will require high speed processors for implementation as well as high run time. The complexity is given in terms of no. of users K, the frame length Nb. The no. of Rake fingers L, the spreading factor N, the number of samples per chip Ns and the number of stages for multistage receiver s. The computational complexity of PIC detector CPIC can be expressed as given below[12]:
The computational complexity of conventional detector is linear with number of users K. It is clear that the computational requirements of PIC method is much more than conventional method. Therefore, in situations, when BER of both the detectors is same, this computational requirement can be saved by making a judicious choice to conventional detector.
The main aim of this proposed switched detector is to dynamically select the detector according to channel conditions. As channel conditions continuously fluctuate, taking one detector for all the situations will not be certainly a good solution. Therefore, our proposed detector instead of using one detector in all the situations, makes a choice between two detectors. The conceptual block diagram of our proposed switched mode detector is shown in Fig.1. The receiver first processes the incoming signal with a bank of matched filters. Next, it performs certain necessary estimations using the output of matched filter. These estimates are then used to decide whether to perform multiuser detection (MUD). If so, the PIC detection will be performed. Otherwise, the receiver bypasses the PIC detection filter operations and symbol decision is made. The key idea is that PIC detector will be used only when MAI is more where its performance is better than matched filter.
In a synchronous CDMA system with K users and processing gain G, bit error probability for matched filter is given by [2]
Where 
is signal to
noise ratio and Q(.) is the complementary Gaussian error function. The bit
error probability in a PIC detector consisting of s stages is given by:
The proof of (7) is given in Appendix A. The switching to PIC detector takes place only when its BER becomes lower than matched filter detector, otherwise detection is done using matched filter detector to save computation time. Therefore the switching to PIC detector occurs when
Pb2 < Pb1 (8)
IV. Simulation results and conclusion:
In fig. 2, we have shown the simulation results for comparing the linear and nonlinear multiuser detection algorithms with the conventional method. As clear from the figure, for low SNR value, the BER of conventional method is almost same as any multiuser detection method, therefore conventional method can be used, as it is least complex among all and already in use. For higher SNR values, BER of nonlinear methods i.e. SIC or PIC is lower than linear methods i.e. decorrelator and Minimum Mean Square Error (MMSE). We consider nonlinear multiuser detector method i.e. PIC detector in our switching detector as nonlinear methods give less BER than linear methods. Out of two nonlinear methods, PIC detector gives less BER and delay requirement over SIC method. Therefore, it prompts us to take PIC detector as multiuser detector in our proposed algorithm.
As shown in fig. 3, for low value of SNR, BER offered by conventional and SIC method is almost same. Therefore, at low values switched mode detector switches to conventional method keeping complexity to minimum level. When SNR increases, then switched mode detector uses PIC method to minimize BER or increasing capacity, but at the expense of increase in computational complexity. In fig. 4, BER vs. number of users is plotted. It is clear that when number of users is less, the BER offered by conventional method is almost same as PIC method and therefore, conventional method may be used to minimize the computational requirement. But as the number of users increase, effect of MAI will be more and in this situation multiuser detection method (i.e. PIC method) is used to minimize BER or increasing capacity. In real situations, when traffic on the channel e.g. during morning and late night hours or channel is less noisy, our proposed detector will use conventional method to save the computational requirements. This can be seen that the computational complexity will be certainly less than if PIC detector is used always irrespective of channel conditions. Therefore, this detector will reduce complexity by making a choice between two detectors.
Fig. 3: BER vs. SNR comparison for proposed detector with Matched
filter detector and nonlinear detector. (proposed detector switches to
PIC detector when BER of matched filer is more than PIC detector)
Fig. 4: BER vs. No. of users of proposed detector with conventional detector
and PIC detector. (proposed detector switches to PIC as no. of users
are more than 5 where BER of matched filter detector is much more than
PIC detector for SNR=8 dB)
Appendix A:
PIC uses the matched filter detector to detect all of the signals. The decision variables Zi, as seen in figure A-1, are the decision variables used for decoding by the conventional receiver. These decision variables are then used to regenerate the user signals and cancel it from the received signal to isolate the user of interest. The modified received signals are once again fed through the matched filter of the user of interest and another set of decision variables Zi’ is obtained. This process forms the first stage of parallel- cancellation. Multiple stages can be performed to increase the performance of the system as shown in Fig. A-1.
Fig. A-1: Cascade of Parallel cancellers
The Zi represents the decision variable for the ith user at the output of the conventional
detector and is given by
These decision variables are then used to regenerate the user signals, which are cancelled
from the received signal to form a modified received signal. The modified received signal
becomes
The decision variable for the first stage for the ith user now becomes
This completes the first stage cancellation. To cascade one more stage of cancellation, the
new decision variables obtained above are used in the same manner as before to regenerate a more accurate version of the user signals, which are then cancelled from the
received signal. This process can be repeated for s stages to obtain better results. Further
analysis of the decision variables become very difficult and very complicated to follow.
The BER can be expressed as:
References:
1. Moshavi S, “Multi-user detection for DS-CDMA communications”, IEEE communication magazine, October 1996; 137-150.
2. Proakis JG. Digital Communications. Mc Graw Hill: New York, 4th edn, 2000.
3. Verdu S, “ Minimum Probability of Error for Asynchronous Gaussian Multiple Access Channels,” IEEE Transactions on Information Theory 1986; 32(1): 85-96.
4. Xie Z, Short R, Rushforth C, “ A family of suboptimum detectors for coherent multiuser communications,” IEEE journal on selected areas in communications 1990; 5:683-690.
5. Lupas R, Verdu S, “ Linear multiuser detectors for Synchronous Code Division Multiple Access,” IEEE Transactions on Information Theory 1989; 35(1): 123-136.
6. Kiran, Tse DNC, “ Effective Interference and Effective Bandwidth of Linear Multiuser Receivers in Asynchronous CDMA systems,” IEEE Transactions on Information Theory 2000; 46(4): 1426-1447.
7. EE-LIN Kuan and Lajos Hanzo, “ Burst-by-Burst Adaptive Multiuser Detection CDMA: A Framework for Existing and Future Wireless Standards,” Proceedings of IEEE, Vol. 91, No. 2, Feb. 2003.
8. P.Patel and J. Hotzman, “Analysis of a simple Successive Interference Cancellation Scheme in a DS/CDMA System,” IEEE Transactions on Selected Areas in Communications; vol. 12, no. 5, June 1994, pp. 796-807.
9. M.K.Varanasi and B. Aazhang, “ Multistage detection in Asynchronous Code Division Multiple Access Comm,” IEEE Transactions on Communications, vol. 38, No. 4, Apr. 1990, pp. 509-19.
10. Fan M, Siu K Y, “ A Dual mode multiuser detector for CDMA systems,” IEEE journal on selected areas in communications 2002; 20(2): 303-309.
11. D. Divsalar, M.K.Simon and D. Rapheli, “Improved Parallel Interference Cancellation for CDMA,” IEEE Transactions on Communications, vol. 46, No. 2, Feb. 98, pp. 258-268.
12. R.M. Buehrer et al., “ A Simulation Comparison of multiuser receivers for cellular CDMA,” IEEE Transactions on Vehicular Technology, vol. 49, no. 4, pp. 1065-1085, July 2000.
Technical College - Bourgas,
All rights reserved,
© March, 2000